public class No012 {
    /**
     * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
     * 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
     * 如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
     * 例如
     * [[a,b,c,e],
     * [s,f,c,s],
     * [a,d,e,e]]
     * 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
     * 因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
     */
    public static void main(String[] args) {
        System.out.println(hasPath(("ABCEHJIG" +
                                    "SFCSLOPQ" +
                                    "ADEEMNOE" +
                                    "ADIDEJFM" +
                                    "VCEIFGGS").toCharArray(), 5, 8, "SGGFIECVAASABCEHJIGQEMS".toCharArray()));
    }

    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        boolean[][] visit = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (find(matrix, rows, cols, str, i, j, 0, visit)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean find(char[] matrix, int rows, int cols, char[] str, int row, int col, int s, boolean[][] visit) {

        if (s >= str.length) return true;
        if (row < 0 || col < 0 || row >= rows || col >= cols || matrix[row * cols + col] != str[s] || visit[row][col]) {
            return false;
        }
        visit[row][col] = true;
        boolean hasPath = find(matrix, rows, cols, str, row + 1, col, s + 1, visit)
                || find(matrix, rows, cols, str, row, col + 1, s + 1, visit)
                || find(matrix, rows, cols, str, row - 1, col, s + 1, visit)
                || find(matrix, rows, cols, str, row, col - 1, s + 1, visit);
        visit[row][col] = false;
        return hasPath;
    }
}
